
public class Solution160 {

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        // p1 指向 A 链表头结点，p2 指向 B 链表头结点
        ListNode p1 = headA, p2 = headB;
        while (p1 != p2) {
            // p1 走一步，如果走到 A 链表末尾，转到 B 链表
            if (p1 == null) p1 = headB;
            else            p1 = p1.next;
            // p2 走一步，如果走到 B 链表末尾，转到 A 链表
            if (p2 == null) p2 = headA;
            else            p2 = p2.next;
        }
        return p1;
    }
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        ListNode a = headA;
        ListNode b = headB;
        ListNode res = null;
        int cnta = 0,cntb = 0;
        while(true){
            //一直往后走，相等退出。
            if(a != null && b != null){
                //先判断覆盖头节点一样的情况
                if(a == b){
                    res = a;
                    break;
                }
                a = a.next;
                b = b.next;
            }
            //任意一方到达最后，改方向
            if(a == null){
                a = headB;
                cnta++;
            }
            if(b == null){
                b = headA;
                cntb++;
            }
            //任意一方改方向达到两次代表没有公共节点
            if(cnta >= 2 || cntb >= 2){
                break;
            }

        }
        return res;
    }
}